Distributed storage clusters may be built of commodity computers that can deliver high performance, availability, and scalability for data-intensive applications at a reduced cost compared to monolithic disk arrays. Storage clusters may achieve high availability and durability by storing multiple replicas of every object. The locations of those replicas may be constrained by many factors, such as object policy requirements, object access patterns, and dynamic characteristics of the storage system (such as capacities and performance of locations and network links). Due to variability of these factors, a storage system, that uses storage clusters, may have to periodically change replica locations of some objects by performing replications from an existing location to a new one. In some distributed storage systems, the number of objects that require replication, at any given moment, may be large.